var shellSortArray = function (nums) {
  const N = nums.length;
  // 使用 Knuth 增量序列
  let h = 1;
  while (h < N / 3) {
    h = 3 * h + 1; // 动态定义间隔序列 1,4,13,40,121,...
  }

  for (; h >= 1; h = h / 3) {
    // 将数组变成h有序（h递减为1）
    for (let i = h; i < N; i++) {
      // 将nums[i] 插入到nums[i-h], nums[i-2*h], nums[i-3*h]... 中
      for (let j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
        let temp = nums[j];
        nums[j] = nums[j - 1];
        nums[j - 1] = temp;
      }
    }
  }
};

var shellSortArray2 = function (nums) {
  // 增量序列就直接用折半法
  const N = nums.length;
  for (let gap = N / 2; gap > 0; gap /= 2) {
    for (let i = gap; i < N; i++) {
      let temp = nums[i];
      let j = i;
      for (; j >= gap && nums[j - gap] > temp; j -= gap) {
        nums[j] = nums[j - gap];
      }
      nums[j] = temp;
    }
  }
};
